Binary Tree

二叉树的定义、实现、遍历、输出、应用。

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

struct BiTNode {
	int data;
	BiTNode *lchild;
	BiTNode *rchild;
};

class BinaryTree {
private:
	BiTNode *bt;
	int RCreate(BiTNode *p, int k, int end);
public:
	void CreateBiTree(int end);
	BinaryTree() { bt = NULL; }
	void Release(BiTNode *root);
	~BinaryTree();
	int PreTraverse(BiTNode *p);
	int InTraverse(BiTNode *p);
	int PostTraverse(BiTNode *p);
	void PreOrderTraverse();
	void InOrderTraverse();
	void PostOrderTraverse();
	void LevelOrderTraverse();
	void LeafCount();
	void BiTreeDepth();
	BiTNode *GetTreeNode(int item, BiTNode *lptr, BiTNode *rptr);
	BiTNode *CopyTree(BiTNode *p);
	int CompareTree(BiTNode *t1, BiTNode *t2);
	BiTNode *GetRoot();
	void BiTreeDisplay(BiTNode *bt, int level = 1);
};
//创建二叉树递归函数
int BinaryTree::RCreate(BiTNode * p, int k, int end) {
	BiTNode *q;
	int e;
	cin >> e;
	if (e != end) {
		q = new BiTNode;
		q->data = e;
		q->lchild = NULL;
		q->rchild = NULL;
		if (k == 1) p->lchild = q;
		if (k == 2) p->rchild = q;
		RCreate(q, 1, end);
		RCreate(q, 2, end);
	}
	return 0;
}
//按先序序列创建二叉树
void BinaryTree::CreateBiTree(int end) {
	cout << "请按先序序列的顺序输入二叉树，0为空指针域标志：" << endl;
	BiTNode *p;
	int e;
	cin >> e;
	if (e == end) return;
	p = new BiTNode;
	if (!p) {
		cout << "申请内存失败！" << endl;
		exit(-1);
	}
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;
	bt = p;
	RCreate(p, 1, end);
	RCreate(p, 2, end);
}
//先序遍历递归函数
int BinaryTree::PreTraverse(BiTNode *p) {
	if (p != NULL) {
		cout << p->data << ' ';
		PreTraverse(p->lchild);
		PreTraverse(p->rchild);
	}
	return 0;
}
//中序遍历递归函数
int BinaryTree::InTraverse(BiTNode *p) {
	if (p != NULL) {
		InTraverse(p->lchild);
		cout << p->data << ' ';
		InTraverse(p->rchild);
	}
	return 0;
}
//后续遍历递归函数
int BinaryTree::PostTraverse(BiTNode * p) {
	if (p != NULL) {
		PostTraverse(p->lchild);
		PostTraverse(p->rchild);
		cout << p->data << ' ';
	}
	return 0;
}
//销毁二叉树递归函数
void BinaryTree::Release(BiTNode *root) {
	if (root != NULL) {
		Release(root->lchild);
		Release(root->rchild);
		delete root;
	}
}
//析构函数
BinaryTree::~BinaryTree() {
	Release(bt);
}
//非递归先序遍历二叉树
void BinaryTree::PreOrderTraverse() {
	cout << "先序（非递归）遍历二叉树：";
	BiTNode *p = bt;
	stack<BiTNode> s;
	while (p || !s.empty()) {
		if (p) {
			cout << p->data << ' ';
			s.push(*p);
			p = p->lchild;
		}
		else {
			p = new BiTNode;
			*p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}
//非递归中序遍历二叉树
void BinaryTree::InOrderTraverse() {
	cout << "中序（非递归）遍历二叉树：";
	BiTNode *p = bt;
	stack<BiTNode> s;
	while (p || !s.empty()) {
		if (p) {
			s.push(*p);
			p = p->lchild;
		}
		else {
			p = new BiTNode;
			*p = s.top();
			s.pop();
			cout << p->data << ' ';
			p = p->rchild;
		}
	}
	cout << endl;
}
//非递归后序遍历结点类型
struct BiTNode1 {
	BiTNode *bt;
	int tag;
};
//非递归后序遍历二叉树
void BinaryTree::PostOrderTraverse() {
	cout << "后序（非递归）遍历二叉树：";
	BiTNode *p = bt;
	stack<BiTNode1> s;
	BiTNode1 *temp;
	while (p || !s.empty()) {
		if (p) {
			BiTNode1 *t = new BiTNode1;
			t->bt = p;
			t->tag = 1;
			s.push(*t);
			p = p->lchild;
		}
		else {
			temp = new BiTNode1;
			*temp = s.top();
			s.pop();
			if (temp->tag == 1) {
				temp->tag = 2;
				s.push(*temp);
				p = new BiTNode;
				p = temp->bt->rchild;
			}
			else {
				cout << temp->bt->data << ' ';
				p = NULL;
			}
		}
	}
	cout << endl;
}
//层次遍历二叉树
void BinaryTree::LevelOrderTraverse() {
	cout << "层次遍历二叉树：";
	queue<BiTNode> q;
	BiTNode *t;
	if (bt) {
		q.push(*bt);
		while (!q.empty()) {
			t = new BiTNode;
			*t = q.front();
			q.pop();
			if (t) cout << t->data << ' ';
			if (t->lchild) q.push(*t->lchild);
			if (t->rchild) q.push(*t->rchild);
		}
	}
	cout << endl;
}
//计算叶子的个数递归函数
void Leaf(BiTNode *p, int &count) {
	if (p) {
		Leaf(p->lchild, count);
		Leaf(p->rchild, count);
		if (p->lchild == NULL && p->rchild == NULL) count++;
	}
}
//后序遍历计算叶子的个数
void BinaryTree::LeafCount() {
	int count = 0;
	Leaf(bt, count);
	cout << "叶子的个数为" << count << endl;
}
//计算深度递归函数
void Depth(BiTNode *p, int level, int &depth) {
	if (p->lchild) Depth(p->lchild, level + 1, depth);
	if (p->rchild) Depth(p->rchild, level + 1, depth);
	if (level > depth) depth = level;
}
//后序遍历计算深度
void BinaryTree::BiTreeDepth() {
	int depth = 0;
	if (bt) {
		Depth(bt, 1, depth);
	}
	cout << "二叉树的深度为" << depth << endl;
}
//获取二叉树的一个结点
BiTNode *BinaryTree::GetTreeNode(int item, BiTNode * lptr, BiTNode * rptr) {
	BiTNode *p = new BiTNode;
	p->data = item;
	p->lchild = lptr;
	p->rchild = rptr;
	return p;
}
//先序遍历复制一棵二叉树
BiTNode *BinaryTree::CopyTree(BiTNode *p) {
	BiTNode *newlptr, *newrptr;
	if (p == NULL) return NULL;
	if (p->lchild) newlptr = CopyTree(p->lchild);
	else newlptr = NULL;
	if (p->rchild) newrptr = CopyTree(p->rchild);
	else newrptr = NULL;
	bt = GetTreeNode(p->data, newlptr, newrptr);
}
//先序遍历判断两棵二叉树是否相等
int BinaryTree::CompareTree(BiTNode * t1, BiTNode * t2) {
	if (t1 == NULL && t2 == NULL) return 1;
	else if (t1->data == t2->data&&CompareTree(t1->lchild, t2->lchild) && CompareTree(t1->rchild, t2->rchild)) return 1;
	else return 0;
}
//获取根结点
BiTNode* BinaryTree::GetRoot() {
	if (bt != NULL) return bt;
	return NULL;
}
//反中序递归横向树状显示一棵二叉树
void BinaryTree::BiTreeDisplay(BiTNode * bt, int level) {
	if (bt) {
		BiTreeDisplay(bt->rchild, level + 1);
		for (int i = 0; i < level; i++) cout << "  ";
		cout << bt->data << endl;
		BiTreeDisplay(bt->lchild, level + 1);
	}
}

int main() {
	BinaryTree bit;
	BinaryTree bit1;
	while (1) {
		bit.CreateBiTree(0);
		bit.BiTreeDisplay(bit.GetRoot(),0);

		cout << "先序（递归）遍历二叉树：";
		bit.PreTraverse(bit.GetRoot());
		cout << endl;

		cout << "中序（递归）遍历二叉树：";
		bit.InTraverse(bit.GetRoot());
		cout << endl;

		cout << "后序（递归）遍历二叉树：";
		bit.PostTraverse(bit.GetRoot());
		cout << endl;

		bit.PreOrderTraverse();
		bit.InOrderTraverse();
		bit.PostOrderTraverse();
		bit.LevelOrderTraverse();

		bit.LeafCount();
		bit.BiTreeDepth();

		bit1.CopyTree(bit.GetRoot());
		bit1.BiTreeDisplay(bit1.GetRoot(), 0);
		if (bit1.CompareTree(bit.GetRoot(), bit1.GetRoot())) cout << "相等，拷贝成功" << endl;
		cout << endl;
	}
	return 0;
}